package algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author MaGuangQi
 * @description https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 * 第102题
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 结果[[3],[9,20],[15,7]]
 * @date 2020-07-06 23:38
 **/
public class LevelOrder102 {

    /**
     * 解法一: 使用BFS,(广度优先遍历) 这道理考察的是BFS的使用
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        //Set visited =new HashSet();
        //如果是图的话,需要判断元素是否已经访问过了
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //队列保存每层的节点
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            //巧妙的地方,queue的长度恰好是当前层元素的个数
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                //循环取出当前层元素,放到list中
                TreeNode curNode = queue.poll();
                level.add(curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            //把当前层的元素加入
            result.add(level);
        }
        return result;
    }

    /**
     * 解法二: 这道题其实也可以使用DFS来解决.
     * 深度优先遍历
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 结果[[3],[9,20],[15,7]]
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {

        if (root == null) {
            return result2;
        }
        dfs(root,0);
        return result2;
    }

    /**
     * 全局属性
     */
    private List<List<Integer>> result2 = new ArrayList<>();

    /**
     * 递归的形式(深度优先遍历)
     * 二维数组结果中,假设有3层,那么二维数组的长度就是3.
     * 在每次遍历的时候,当前level恰好是数组的长度
     * 例如: 当前第一层, 结果是[[3]],list长度是1
     * 第二层,结果是[[3],[9,20]]
     * <p>
     * 每次遍历的时候,先放一个level空数组,然后把数组值填满
     * <p>
     * 函数作用,深度优先遍历,遍历node
     *
     * 递归前序遍历 根->左->右
     *
     */
    public void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        //巧妙的地方, 这里是先创建一个空list,然后再把当前值加入
        if (result2.size() < level + 1) {
            //先初始化一个空数组
            List<Integer> curNode = new ArrayList<>();
            result2.add(curNode);
        }
        //将当前节点值加入list
        result2.get(level).add(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}
